package com.javabasic.algorithm.leetcode;

public class LongestPalindromicSubstring {

    /**
     * 解题失败： 不能采用将字符串反转然后取最长公共字串
     * 样例："aacdefcaa"
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }
        int len = s.length();
        int[][] dp = new int[len+1][len+1];
        StringBuilder str = new StringBuilder(s);
        str = str.reverse();
        String result = "";
        int tag = -1, max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s.charAt(i) == str.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                if (dp[i+1][j+1] > max) {
                    max = dp[i+1][j+1];
                    tag = i;
                }
            }
        }
        return s.substring(tag-max+1,tag+1);

    }

    int max = 1;
    int tagIndex = 0;

    /**
     * 解法一：由中心向两边扩展，注意中心可能是一个字符也可能是两个字符，对应的回文字符串长度就是单数和复数
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }
        int len = s.length();

        String result = "";
        for (int i = 0; i < len-1; i++) {
            getLongestPalindromeStr(s,i,i);
            getLongestPalindromeStr(s,i,i+1);
        }
        result = s.substring(tagIndex,tagIndex+max);
        return result;
    }

    private void getLongestPalindromeStr(String s, int left, int right) {
        int len = s.length();
        while (left >=0 && right < len && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        if (right-left-1 >= max) {
            max = right-left-1;
            tagIndex = left+1;
        }
    }


    /**
     * 解法二：动态规划解法
     * dp[i][j] 表示 字串 i-j 是否是回文字符串，是为1 不是为0
     * dp[p][q]是否是回文串，
     * 当p+1 == q 时，只要s[p]==s[q] 那么dp[p][q]=1
     * 当p+1 < q 时, 要两个条件 s[p]==s[q] && dp[p+1][q-1]是回文串
     *
     * 特殊：dp[i][i] = 1
     *
     *
     * @param s
     * @return
     */
    public String longestPalindrome3(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }
        int len = s.length();
        int dp[][] = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        String result = "";
        for (int i = 1; i < len; i++) { // 长度 i+1
            for (int j = 0; j < len-i; j++) {
                if (s.charAt(j) == s.charAt(j+i)) {
                    if (i == 1) {
                        dp[j][j+i] = 1;
                    } else {
                        if (dp[j+1][j+i-1] == 1) {
                            dp[j][j+i] = 1;
                        }
                    }
                }
                if (dp[j][j+i] == 1 && i+1 > max) {
                    max = i+1;
                    tagIndex = j;
                }
            }
        }
        result = s.substring(tagIndex,tagIndex+max);
        return result;
    }
}
